perm filename 4R.DOC[P,JRA] blob
sn#115470 filedate 1974-08-09 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00026 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 FORWARD
C00004 00003 INTRODUCTION
C00010 00004 GOALS
C00017 00005 THE RUNTIME SYSTEM
C00027 00006 GENERAL OUTLINE OF THE HAL SYSTEM
C00034 00007 EXAMPLE DIALOG WITH THE HAL SYSTEM
C00043 00008 THE HAL SOURCE LANGUAGE
C00064 00009 CONTROL STRUCTURES
C00069 00010 ON MONITORS
C00078 00011 DATA STRUCTURES
C00082 00012 ALGEBRAIC DATATYPES
C00091 00013 ARITHMETIC
C00096 00014 SOME EXAMPLES OF ARITHMETIC EXPRESSIONS
C00097 00015 MOTION SPECIFICATIONS
C00106 00016 OPTIONS FOR MOVES
C00114 00017 COMPLEX MOVES
C00118 00018 SEARCHES
C00123 00019 DEVICE CONTROL
C00128 00020 WORLD MODEL SPECIFICATION
C00139 00021 USES OF THE WORLD MODEL
C00141 00022 OVERVIEW OF THE RUNTIME
C00142 00023 CONTROL STRUCTURES
C00149 00024 INTERPRETABLE CODE
C00158 00025 DATA STRUCTURES
C00165 00026 TRAJECTORIES not yet ready for perusal
C00192 ENDMK
C⊗;
FORWARD
This document describes the new hand language, HAL. It was
written by Robert C. Bolles, Raphael A. Finkel, Richard L. Paul, and
Russell H. Taylor.
The English language has no neuter personal pronoun; without
any implication of sexism we use the feminine form in its place.
Work supported, in part, by the hand-eye table.
The views and conclusions contained in this document are
those of philosophical inquiry and should not be interpreted as
necessarily repesenting the official policies, either expressed or
implied, of any of the funding agencies.
INTRODUCTION
The development of mechanical manipulators during the Late
Middle Ages of 1948 soon led to the realization that most tasks
require position and force feedback. For the last ten years,
computers have been used as a controlling agent. This has led to
sophisticated servo programs which periodically compute an
incremental controlling signal from comparison of current manipulator
status against the planned status.
Elementary languages have been built for the purpose of
automating tasks more lengthy than simple motions. These languages
have much the flavor of assembly languages; primitive commands
involve those necessary for planning various kinds of motions, for
controlling the execution of the computed plans, and for simple
response to error conditions.
APT is one highly successful system for the automation of
parts-machining tasks. It provides open-loop control of metal
cutting machines and allows precision cutting along curved lines and
accurate workpiece positioning. The principal failings of APT
involve its poverty of descriptive ability for complicated motions,
the resulting limitation on the type of tasks which it can
accomplish, and its restriction to metal cutting machines.
Another example of a system for manipulator control is WAVE
at Stanford. It includes two Scheinman electrical arms and software
for preparing moderately complex plans. The most impressive
accomplishment of this system has been the assembly of a water pump,
which was done with one arm, and optionally made use of visual
feedback. Further achievements have included a primitive two-arm
task: the assembly of a hinge. WAVE currently can produce
independent plans for the two arms. The only form of coordination is
achieved by halting one arm and starting the other one. The model of
world knowledge contained in the system is quite limited: A small
number of hand positions can be remembered; each of these positions
can be associated with an "offset" between planned position and real
position. This information is obtained during the actual execution
of a plan,and allows run-time modification of trajectories. The
sophistication of the control structure is limited; there are only
simple jumps, including conditionals on error conditions. When a
plan fails due to excessive requests on hardware ability, the user
may request the continuation of the plan. WAVE also has a clumsy
interface with SAIL, which is a high-level algol-like language; thus,
in principal, it can take advantage of SAIL's algebraic power.
None of the currently available task-automation languages is
capable of efficiently sequencing tasks or planning other strategy
for the execution of a task; they only can translate explicit
instructions into machine-executable form. In this sense they can be
thought of as "assembly languages"; some of them are rather fancy,
with a macro facility, a few named variables, and some simple
arithmetic, but none can be called a high-level language.
The availability of new types of hardware (for example,
force-sensing wrists) and the increasing complexity of the tasks we
wish to perform, as well as the recognized failings of WAVE, have led
us to the design of a new hand language, which is called HAL. It is
a very high level language for the specification of manipulatory
tasks (especially assembly tasks) in a world of several arms and
other devices. The following pages contain a description of HAL.
GOALS
A full language for planning manipulatory tasks of the
complexity required for assembly needs many features, some of which
do not exist in any current system. We have identified these goals:
HIGH LEVEL LANGUAGE FEATURES
1) The language must be able to describe those things
important to the programmer. This implies that there should be
datatypes natural to the tasks at hand. Principally, there should be
a datatype whose value is a location-orientation in 3-space.
Secondarily, there should be vectors and scalars. Arithmetic
operations should be defined on these datatypes to make them useful.
2) We want to write entire programs in a natural manner. The
machine-language aspect of current manipulation languages makes it
cumbersome to write long programs in any structured way. What is
desired is a language which lends itself to a more systematic and
perspicuous programming style. Algol-like control structures would be
a vast improvement over assembly-like straight code with jumps.
3) Simultaneous execution of several processes should be
available. A general mechanism for simultaneity is desired.
FULL MOTION SPECIFICATIONS
1) Experience with WAVE has shown that calculating
trajectories is a desirable feature, although a time-consuming one.
Therefore, a motion should be calculated in a "compilation" step, and
executed at a later time, perhaps repeatedly. This leads to a clear
distinction between compile-time and runtime.
2) Since we are aiming for a system of use on the factory
floor, and since a large time-sharing machine is incapable of
supporting real-time control over many devices, execution of plans
should take place under the control of a small computer (like a
PDP-11), many of which could be distributed in the work area.
Trajectory planning, however, is not real-time constrained, and is
better done on a large computer (like a PDP-10).
3) Since locations are not known exactly during planning of a
trajectory, there should be a clear distinction between planned
values and runtime values. Planned values will be used for
trajectory calculation; at runtime, these trajectories will be
modified if necessary to account for any discrepancies.
4) The user should be able to demand that a trajectory pass
through certain intermediate points. The primary use of this is to
avoid collisions (especially with the table) during the motion. It
is also useful for specifying complicated motions, such as those
necessary to accomplish spray-painting.
5) It is necessary to test for a wide range of exceptional
conditions during arm motion and to take appropriate action as soon
as any of them occurs. These conditions could include excessive
force being exerted, excessive closeness of the arms, completion of
some related task being done independently by other devices, an
interrupt generated by the user, a certain time arriving, and a
temperature senser reaching a critical point. The appropriate
actions might be to start up a new concurrent process, to terminate
something already active, to notify the user, or to file away a
statistic in a table somewhere. It is also useful to change the
nature of the test during a motion, if different segments require
different types of monitoring. This concept can be generalised to
include the modification of a motion during its execution to
accomodate to changing conditions. In any case, it should be easy
for the user to specify exactly what is being tested, what the scope
of the test is (that is, when should it start and when should it
end), and what to do if it triggers.
THE RUNTIME SYSTEM
1) The runtime system (which, as previously mentioned, is
intended to reside in a minicomputer) must support simultaneous
executions of several processes. Three basic types of process have
been identified: An interpreter, which does arithmetic; a servo,
which controls one joint of one device; and a monitor which
continually examines conditions. These must be managed in some
(simple) scheme of time-sharing with guaranteed response for the
latter two types of process.
2) There must be enough information available at runtime for
the proper modification of trajectories immediately before they are
executed.
3) The system must be capable of using vision and other yet
unpredictable forms of feedback must Vision would be quite useful in
searching for objects and testing for adequacy of assembly. It is
conceivable that vision will be used for the servoing of an arm; this
implies that the feedback loop must be active during motions as well
as when the world is stationary. Other dynamic feedback (like
force-sensing wrists) could make the capabilities of the arms much
greater in dealing with non-rigid materials like cloth or rope. What
is needed is a way of specifying calls to these "external" devices so
that when they become available, they can be meshed into the system
without much difficulty.
4) There should be a way to investigate the contents of the
runtime system, both variables and code, in order to patch simple
mistakes discovered during the course of a production run. This
feature would be especially useful for debugging the compiler.
ADVANCED LANGUAGE FEATURES
1) Assembly tasks require that one object be affixed to
another. We wish to model this by having a semantic attachment
between objects. When one moves, the second one should move (that is,
its planning value should be modified) accordingly. This
"attachment" concept carries over to the runtime system, which does
the equivalent modifications of the actual values. This saves the
user untold bookkeeping operations to determine where an object is
after its base has been moved.
2) Attachment is not the only world information that should
be kept in the compiler. Other desirable information includes not
only all planning values but also information like the accuracy
within which the planning value is known, how heavy objects are, how
many faces an object has on which it can rest, how wide the fingers
of an arm should open to grasp it.
3) Ability to assist in the preparation of a program. This
is a wide-ranging issue, which involves at least these goals: To be
able to compile a piece of code and then to try it on the spot; to
delete or replace sections of previous code; to ask the arms for
status information during the coding process itself for the purpose
of setting constants and for implementation of a "learning by
showing" strategy. It should be easy for the user to recover from
errors discovered during any phase of debugging. The compiler itself
should make a great number of semantic checks, like assuring that a
proposed motion will not hit some object (although this is a
difficult problem which has not yet been satisfactorily solved), or
that simultaneous independent motions are not being requested for the
same device. Use of the graphics system should be made to depict the
world as the compiler sees it during compilation.
→→→→→RCB should rewrite 4:
4) There should be a program library. What is needed is to
be able to program frequently-needed procedures, like "PUT IN A
SCREW", in some generality, and then to be able to use them in the
future by supplying from the model whatever information was left out.
A solution is to have library routines capable of being conditionally
expanded, depending on the state of the planned world at the moment,
so many similar macros can be written together for tasks like "PUT IN
A SCREW AT CENTER OF TABLE", "PUT IN A VERY LONG SCREW", "PUT A
SCREW THROUGH A THIN BOARD", and others, differing not only in the
values of the expected parameters but fundamentally in the method
used to accomplish the task.
5) Ability on the part of the system to automate simple
decisions based on world information. An example would be for the
system to decide where best to locate an object for future work when
the programmer requests that the system pick the place for her.
→→→→→ RHT should rewrite 6:
6) Ability to say "BIND X TO Y" and expect that the knowledge
contained about x and y suffices to allow the compiler to generate
all the code needed for the attachment of the two objects, including
what the means of fastening is to be, where it will be done, and
exactly what sequence of operations is necessary to accomplish the
task. What we are asking for is a program capable of strategy
formation for the achievement of assembly tasks based on incomplete
knowledge, incorporating whatever fragmentary knowledge is available
about the world, techniques of assembly, what library routines are
available, what sort of global costs and success rates can be
expected for different approaches. This strategist (or sequencer,
perhaps) should be able to query the user concerning details which
are essential for the planning, and should be able to come up with
code recognizable as something the user might have typed in had he
been willing and able to go to the trouble.
GENERAL OUTLINE OF THE HAL SYSTEM
HARDWARE
Currently two Stanford Electric Arms, built by Victor
Scheinman, are available. They are called YELLOW and BLUE. Each has
six joints and a hand which can open and close. The joints are
controlled by electrical motors; there is feedback of position and
velocity for each joint. The motor drives are computed and sent to
the arm via a digital-to-analog converter; the feedback signals are
routed through an analog-to-digital converter back to the computer.
There is a small electically-powered screwdriver which can be
held in the mechanical hands. It can operate in either direction
over a range of speeds.
A vise has been designed for holding parts during assembly.
It is powered by compressed air.
Oh, yes. We also have a few television cameras.
HAL resides on two computers: The PDP-10 for all planning,
and a PDP-11 for the execution of the plans. The former is run as a
timesharing computer (under a modified DEC system); the latter is
operated in a stand-alone mode under the HAL runtime system. Each
computer is capable of generating an interrupt in the other, and the
PDP-10 has complete control over the PDP-11 console and unibus.
SOFTWARE
The SUPERVISOR is the top level of the system. It runs on
the PDP-10 and provides an interface between the user and the other
parts of the system: 1) listening to the user's console and
interpreting input in a special command language; 2) controling the
compiler, starting it and relaying its error messages back to the
user; 3) signalling the loader when it is necessary to place compiled
code into the PDP-11; 4) handling the runtime interface to the PDP11.
Each of these modules is discussed below.
The USER sits at a console and makes requests of HAL. These
fall into several catagories: Compilation, loading, execution of
programs, debugging of code, requesting status information, asking
for immediate arm motion, saving and restoring the state of the world
at safe points, requesting explanation of certain compiler decisions.
The COMPILER reads HAL programs from files (or, optionally,
directly from the user's console) and produces load modules. The
compiler is divided into three phases: The PARSER, the EXPANDER, and
the TRAJECTORY CALCULATOR. The compiler is discussed in detail later.
The LOADER takes the load modules prepared by the compiler
and enters them into the PDP11 runtime system. Address relocation
and linking is done at this time. The loader also sets up the data
area in the runtime interface in the PDP-10; this data includes
output strings, procedure linkages, and information necessary for
diagnostic purposes during runtime. Loading is often done in a
partially incremental fashion, installing new code following
previously loaded code.
The RUNTIME INTERFACE is charged with initiating the PDP-11
program, fielding procedure calls from the running HAL program to
PDP-10 procedures, returning values from these procedures,
interrupting the execution of a program, and fetching values from the
PDP-11 for debugging purposes.
The RUNTIME SYSTEM is the set of programs which reside in the
PDP11. This system includes kernel programs for time-slice cpu
sharing and process control, and a set of dynamically created
processes. These are of three basic types: a) An INTERPRETER
examines the tables prepared by the compiler and executes the numeric
computations requested. When a move is to be started, the
interpreter sprouts a servo for each joint and waits until all these
servos terminate. b) A SERVO handles the motion of one moving joint.
c) A CONDITION-MONITOR repeatedly examines certain conditions
(whatever the programmer has specified). If it should discover that
its condition is satisfied, it sprouts an interpreter to take
appropriate action. The runtime system also includes routines for
communication with the runtime interface. The runtime system is
described in detail later.
EXAMPLE DIALOG WITH THE HAL SYSTEM
Here is a sample conversation a user might have with HAL. It
demonstrates the following features: Typing in source code by hand,
requesting source code to be read from a file, immediate execution
of commands by the arm, return of values from the arm, loading
compiled code into the runtime computer, and executing that code.
The supervisor prompts with the sign "⊃". The material in
the right-hand column is explanatory.
⊃ COMPILE TTY | Request to read in
| from console for compilation.
⊂ type <alt> when done ⊃ | Message from supervisor
MOVE YELLOW | Simple move statement
TO [(20 30 1):(π 0 0)]; | Destination
|
FRAME PLACE1; | Declaration
PLACE1 ← YELLOW; | Assignment
PLACE2 ← PLACE1+(0 0 5); | Assignment
⊂ OK to declare PLACE2 a FRAME? ⊃ YES | Parser error, with option.
$ | End of file (altmode)
⊂ no errors. compiled: TTY(1) ⊃ | Compiler message.
|
⊃ IMMEDIATE | Request for an immediate action
⊂ type <alt> when done ⊃ | Message from supervisor
MOVE YELLOW TO PARK $ | User wants to park the arm
⊂ done ⊃ | And does
|
⊃ EXECUTE | Request to execute compiled code
⊂ loading TTY(1) ⊃ | First, loading to be done
⊂ executing TTY(1) ⊃ | Message at start of execution
⊂ done ⊃ | Message at end of execution
|
⊃ READ PLACE3 ← YELLOW | Request to read hand position
⊂ OK to declare PLACE3 a FRAME? ⊃ YES |
⊂ PLACE3 = [(19.9, 30.1, 1.1):(3.1, 0, 0.1)] ⊃ | Indication of what was set
|
⊃ VALUE PLACE4 | Request for value of variable
⊂ PLACE4 not declared. Declare it a ⊃ | User has chance to fix
⊂ Please retype command ⊃ | simple errors.
⊃ PLANVALUE V1 | Request for planning value
⊂ #(V1) = (3.0, 0, 20.13) ⊃ |
⊃ PLANVALUE V1 ← (4.0, 0, 20.13) | User can change planvalues.
⊃ VALUE V1 ← (4.0, 0, 20.13) | User can change real values.
|
⊃ COMPILE HACK.HAL[1,LOU] | Request for compile from file
⊂ Error in line 310 of HACK.HAL[1,LOU]. | Parser error message
THEN | Gives line with <lf>
CONE | at point of error
Option ⊃ ? | User typed "?"
I: Insert replacement text | A list of options to user
Z: Use line editor to fix |
M: Show more context | This would give entire statement
F: Flush to end of statement |
E: Switch to E | E is a text editor
S: Switch to SOS | SOS is a text editor
Q: Quit. Abort compilation |
Option ⊃ I | User chooses to insert replacement
⊂ type <alt> when done ⊃ | Message from supervisor
THEN DONE | "CONE" changed to "DONE"
$ | End of insertion
⊂ error in line 520 of HACK.HAL[1,LOU]. | trajectory calculator error message
MOVE YELLOW | Only first line of statement given
The desired motion goes out of bounds in joint 3| A bad motion
in the first segment of motion. |
Option ⊃ E | User chooses to edit with E.
⊂ Switching to E. To return, <CTR>XG<CR> ⊃ | Universe is saved for reentry.
⊂ Welcome back to HAL. | Editing done
Compilation of HACK.HAL[1,LOU] aborted⊃ | After an edit, compilation aborts.p
|
⊃ COMPILE HACK.HAL[1,LOU] | Request for recompilation
⊂ No errors. Compiled: TTY(1), HACK.HAL[1,LOU] ⊃| Compilation succeeds.
|
⊃ LOAD | Request to load into servo
⊂ Loaded: TTY(1), HACK.HAL[1,LOU] ⊃ |
|
⊃ STATUS | User wants to know where she is
BLUE at [(19.9, 30.1, 1.1) : (3.1, 0, 0.1)] | Arm location
Compiled: TTY(1), HACK.HAL[1,LOU] | Compilation status
Loaded: TTY(1), HACK.HAL[1,LOU] | Runtime status
|
⊃ EXECUTE | Request for execution
⊂ Executing TTY(1), HACK.HAL[1,LOU] ⊃ |
|
⊃ STATUS | User wants to know where she is
BLUE at [(24.1, 30.1, 5.3) : (3.1, 0, 0)] moving| Arm status
Interpreter at line 320 in HACK.HAL[1,LOU] | Servo status
⊂ Interrupted by red button⊃ | Runtime error message. User
| interrupted motion.
Interpreter at line 180 of HACK.HAL[1,LOU] | Servo status
|
⊃ PROCEED | Request to continue motion
⊂ Joint 4 has excessive force. | Runtime error message.
Interpreter at line 150 of HACK.HAL[1,LOU] | Servo status
|
⊃ DELETE 1 | Request to delete last compilation
⊂ Deleting HACK.HAL from runtime | Removed from runtime
⊂ Deleting HACK.HAL from COMPILATION | Removed from world of compiler
|
⊃ E | Switch to E.
⊂ Switching to E. To return, <CTR>XG<CR>⊃ |
⊂ Welcome back to HAL⊃ |
|
⊃ COMPILE HACK.HAL[1,LOU] | Request for compilation
⊂ No errors. Compiled: TTY(1), HACK.HAL[1,LOU] ⊃| Compilation succeeds
|
⊃ SAVE WORLD IN W1 | User wants world saved in named
⊂ World saved in W1.WLD ⊃ | location; this is done.
|
⊃ RESTORE WORLD FROM W0 | Request to restore previous world
⊂ W0.WLD not found ⊃ | Expander error message
|
⊃ RESTORE WORLD FROM W00 | Request to restore previous world
⊂ done |
Note: TTY(1), HACK.HAL[1,LOU] still compiled. ⊃| This is done, but previous stuff
| is still around.
⊃ BYE | Request to leave the room.
⊂ Final status: | A final status rundown
Load modules ready: TTY(1).HLD, HACK.HLD |
BLUE at [(19.9, 30.1, 1.1) : (3.1, 0, 0.1)] |
Goodbye ⊃ |
EXIT
.
THE HAL SOURCE LANGUAGE
The following is a description of the source language of HAL.
We will discuss the structure of the compiler, and then four areas of
the language: control structures, data structures, motion
specifications, and world model specification.
THE HAL COMPILER
The PARSER reads source code from either the console or a
file. Its purpose is to form parse trees and do some simple
manipulations, such as assigning line numbers, causing listings to
be directed to the appropriate file (if desired), expanding text
macros, and keeping a primitive symbol table. If a syntax error is
discovered, it informs the supervisor, which will give the user
several options, including aborting the compilation, making local
modifications on the spot, or switching temporarily to a text
editor. In many cases, control will be returned to the parser, and
it will continue to create parse trees from the input.
The EXPANDER takes the parse trees produced by the parser and
performs three basic functions: a) (expanding) keeping a world model
for each point of the program, including information on the planned
values for all variables, attachments between objects, and the
assertions which the user has made about the nature of the objects
with which she is dealing. This world model is used to expand those
conditionals which depend on the state of the world (called world
conditionals), and is essential for the proper calculation of
trajectories. A library of previously programmed utility routines is
available to the expander, and it resolves calls on those routines.
b) (binding) The second task of the expander is to pick values for
those variables which the user has left unbound and has explicitly
requested be chosen within given constraints. The expander attempts
to make a good decison as to the best way to bind these variables. If
it is not possible to make this binding without further information,
the expander will query the user for more information. The world
model is used extensively during this process of specification.
Binding also involves branching the program in regions where
locations of objects are not completely known, so that several plans
can be prepared and a runtime check can determine which one to use.
c) (sequencing) The third and hardest task of the expander is to make
global strategy decisions in the case that the user has not specified
even the order in which the assembly is to progress. The expander
must sequence the operations into an order which facilitates the
assembly. The decisions made on this global level interact strongly
with those made on the local level mentioned above; that is one of
the reasons that expanding is a difficult task. The expander can
explain its decisions to the user upon demand.
The output of the expander is a tree very much like that
which it took as input, except that no choices are left; all values
are explicitly specified. This structure is then passed on to the
trajectory calculator.
The TRAJECTORY CALCULATOR takes the expanded code and
computes the required trajectories for the arms. Tables of
interpretable code are generated, for handling arithmetic and
assignment operations, condition monitoring, and graph-structure
building operations (the runtime system keeps track of physical
attachment of objects). For motions, detailed instructions are
emitted specifying how each joint of each arm is to behave, what
computations to make at run-time for the modification of these
trajectories to bring them into correspondence with the current state
of the world (for it happens often that objects are not exactly where
thye were planned to be), and what conditions to monitor during the
motion.
The trajectory calculator also is used to provide information
to the expander. For instance, it can predict the runtime effects
of a given modification of a planned trajectory. This information is
useful to the expander in deciding how many "different" trajectories
must be planned for a given motion request.
There are several errors which the trajectory calculator can
detect. A request might take the arm outside its range, or force a
joint to exceed its velocity limits. It may discover that there is a
possiblity of collision between the two arms, or between the arm and
some object on the table. In order to carry out these tests, it may
request assurance from the user that some object lies within a
certain region, or it may give the user a warning. The world model
is used for much of this calculation. At its discretion, the
trajectory calculator may make some critical motions very slow, so
that an impending collision will be seen before it happens.
The output of the trajectory calculator is stored in binary
files, for loading into the PDP11.
CONTROL STRUCTURES
TRADITIONAL ALGOL STRUCTURES
HAL has many of the traditional ALGOL control structures,
including the statement, the block, the IF-THEN-ELSE conditional,
the WHILE loop, the FOR loop, and the GOTO (which in HAL is written
JUMP. JUMPs will not be implemented at first, because they confuse
the flow analysis needed for maintaining planning values, and because
it is possible to accomplish much without them). The simple
statement can be of several varieties: Assignment, declaration,
manipulation, world modification, condition monitoring. The
assignment statement is of the general form
FROB ← A + (2, 0, 0),
that is, a variable name, a left arrow, and a suitable expression.
The types of expressions available will be discussed under the rubric
of data types. Declarations are allowed anywhere in the code that
other statements are allowed; this facilitates typing in a program
from a terminal. Manipulation, the fundamental purpose of HAL, will
be discussed fully in the section on motion specifications. World
modification actually takes place after every assignment and motion,
but some statements are purely for the purpose of changing the
compiler's notion of the world. All world model specification will
be discussed later. Condition monitoring is discussed below.
A block is a list of statements separated by semicolons,
prefaced by the reserved word BEGIN and closed by the reserved word
END. Blocks are used to enclose a group of statements to form what
syntactically can act as one statement, and provide a means for
keeping variables local to a piece of code. It is possible to name a
block by inserting its name as a string after the BEGIN; this is
useful as a comment, and during debugging provides a way to name
blocks of code. When a block is so named, the name should be repeated
immediately after the END; this provides an easy way to insure proper
matching of BEGINs and ENDs. An example:
BEGIN "SAMPLE"
SCALAR A, I;
A ← 2;
FOR I ← 1 STEP 1 UNTIL 10 DO A ← A*A;
WHILE A > 0 DO
BEGIN "LOOP"
A ← A - 1;
IF A < 5 THEN WRITE(A) ELSE WRITE(A-5)
END "LOOP";
WRITE("DONE")
END "SAMPLE"
COBEGIN-COEND
In addition to these traditional structures, there are also
some special ones for specifying simultaneous independent execution.
The principal device for this is the COBEGIN-COEND pair, which
brackets statements whose execution is meant to begin simultaneouly.
The termination of the block occurs only when each of the statements
in the scope of the COBEGIN has terminated. To achieve simultaneous
coordinated motion, one uses a special form of the move commands
which will be discussed later.
ON MONITORS
It is often desired to monitor some set of conditions
throughout a section of code. A special kind of statement which allows
the user to do this is the ON statement. A simple example is "ON T >
5 DO STOP YELLOW", which while active will monitor the magnitude of T
and if it should become greater than 5 will cause the yellow arm to
stop, if it is moving. An ON monitor has two states: enabled and
disabled. Generally, an ON monitor will be enabled as soon as its
defining statement is executed, and it becomes disabled when its
block is exited. Also, as soon as an ON monitor triggers, it becomes
disabled until explicitly reenabled. Reenabling is done by executing
the statement ENABLE within the conclusion (that is, the statement
following the DO). It is possible to name ON monitors; a monitor
named "CH" will be enabled when a statement of the form ENABLE "CH"
is executed, and is disabled either under the conditions named above
or when it is explicitly turned off by a DISABLE statement. To have
an ON monitor initially disabled, preface the ON with the word DEFER.
The condition which is being tested must be a simple numeric
inequality or equality, possibly using some continually evaluated
function. Boolean combinations are not allowed.
Some examples of ON monitors:
"FUDGE" ON TEMPERATURE > 400 DO OUTPUT("BURNING");
DEFER "WAIT" ON COOKED = 1 DO DISABLE "FUDGE";
ON MARK > 3 DO ENABLE "WAIT";
It should be noted that this ability to enable and disable
monitors explicitly is a non-structured concept; using it will often
lead to unintelligible programs. In any case, scope rules must be
observed; it is not legal to enable or disable a monitor in a
parallel or subsidiary block. This means that two statements,
simultaneously executing inside a COBEGIN block, are not allowed to
interfere with each other's ON monitors. It is generally wise not to
use named ON monitors unless their particular power is needed.
The conclusion of an ON-monitor may be any statement,
including an entire block. The only restriction is that if a motion
statement is the only statement in the conclusion, it must be
surrounded by BEGIN and END. (This is necessary at times to prevent
ambiguity.) Here is a slightly more complex example:
ON DURATION > 5 DO
BEGIN
"BIND" ON FORCE(Z)>10 DO STOP YELLOW;
ON DIST > 3 DO
BEGIN
DISABLE BIND;
VEL ← 40;
END;
END;
The existence of ON monitors raises the question: "when is a
block considered to be finished?" It can happen that all the
executable statements have finished, but some ON monitors remain.
This situation is often sterile; nothing can happen unless one of the
conditions happens to trigger, which may or may not happen.
Therefore, a block is declared finished when no interpreters remain
active within it. This means that if even one ON monitor has caused
an interpreter to start executing (to perform the statements in the
conclusion), then the block is not exited until that interpreter is
done. But a block may be exited while some ON monitors are still
enabled; this automatically disables them.
The user must be wary of the relative speeds at which her
various pieces of code in ON test conclusions get executed. When an
ON test triggers, any initial statements of enabling or disabling are
done immediately, but any arithmetic is scheduled to be done at some
point in the near future. Therefore it is not possible to guarantee
that a critical computation happen immediately. If the user desires,
she may use the word CRITICAL at the start of the conclusion, and
UNCRITICAL at the start of that code which need not be guaranteed
immediate execution. HAL automatically assumes CRITICAL before
statements of enabling and disabling, and UNCRITICAL immediately
following. Caution: if critical computations take too long
(currently about 1 millisecond), there will be a severe runtime
error.
The UNITS statement
Numbers are quite often used for measurements, and many
different systems of measurement exist. The UNITS statement serves
to inform the compiler which units are being used. It uses its own
system for internal consistency, and does any scaling when necessary.
The default units, which the compiler itself uses, are listed first
in the following lists:
Time: milliseconds, seconds, jiffies (that is, thirds: 60ths
of a second), minutes.
(The grain of the runtime is on the order of jiffies).
Distance: centimeters, inches.
Mass: grams, ounces, pounds, kilograms.
Angles: radians, degrees.
Rotations: Euler, Bolles, Taylor, Geomed. (These are explained
in the discussion on dataypes.)
An example:
UNITS SECONDS, DEGREES, TAYLOR;
COMMENTS
As in Algol, comments are prefaced with the word COMMENT and
terminated by a semicolon.
LABELS
A LABEL is a point in the program to which a jump may be
made. Labels also mark some ON-monitors. Labels are not declared. An
example:
FOO: A ← A + 1;
IF A < 100 THEN JUMP FOO;
Labels are in general useful mainly for debugging, and not for
program control, especially since JUMP will not be implemented at
first.
DATA STRUCTURES
DECLARATIONS. PLANNING VALUES. ASSERTIONS.
There are several available types of variables and constants,
as described below in detail. Each variable must be declared
somewhere before it is used; however, it is not necessary that this
declaration be at the top of a block. If a variable which has not
been declared is encountered, an attempt will be made to guess at its
type. (The compiler will, of course, give a warning.) This can lead
to unfortunate results, so it is best to declare all variables. The
compiler keeps track of a "planning value" for each variable. At
first, this value is "undefined"; any expression using an undefined
value itself has undefined value. Planning values become defined
through two mechanisms: Assertions and assignments. The statment
ASSERT X=3 has the compile-time effect of setting the planning value
of X to 3. The statement X←3 has the effect of setting the planning
value to 3 and causing code to be generated for the runtime to set
the value of X to three at this point in the program. If a variable
is changed within a loop, its planning value will be undefined except
between assertions about it and the point in the loop where its value
is changed. The use of JUMPs so complicates the bookkeeping for
planning values that they are highly discouraged. The purpose of
having planning values is severalfold, the most important use being
the calculation of proper trajectories. An example is ASSERT YELLOW
= YPARK, which tells where the yellow arm is. Since at planning time
it is expected that some values will be known only roughly, provision
is made for the runtime to modify all trajectories before executing
them. This is the subject of a later discussion. The planning value
of any variable is accessible to the programmer: #A is the planning
value of the expression A.
ALGEBRAIC DATATYPES
The simplest datatype is the SCALAR, which is internally
represented as a fixed-point number. Scalars are used as time
intervals, space intervals, and as substructures upon which the more
complicated datatypes are built. There is a UNITS statement which
allows the user to set the measurement system she would like to use,
so that a time scalar will be unambiguously interpreted as meaning
seconds, or jiffies, or whatever she wants. Some examples:
SCALAR A, B;
A ← 2.4;
UNITS CENTIMETERS, SECONDS,RADIANS;
B ← 3*A;
The next datatype is the VECTOR. A vector is written as a
triple of scalars separated by commas or blanks. An example is "(2 X
4.3)". Vectors can refer either to location offsets (that is,
translations) or to orientation offsets (that is, rotations). The
context is sufficient to determine which of these meanings is
intended. When a vector refers to a translation, it is understood to
be in TABLE coordinates. When a vector refers to a rotation, it can
either be represented in Euler angles (rotations about z, x', z''),
Bolles angles (rotations about x, y, z), Taylor angles (rotations
about z, x', y'), or Geomed angles (a, b, c, specifying the vector of
rotation whose magnitude is the angle of rotation). The UNITS
statement serves to set a default mode (as well as to determine
whether degrees or radians are being used).
Examples:
VECTOR V1, V2;
V1 ← (3 1 A);
V2 ← V1 ∂ (π 0 0);
A FRAME is a location with an orientation. It has two basic
interpretations, which are closely related: 1) a hand position, and
2) the location and orientation of any object. TABLE is a predefined
frame. (It holds table coordinates). Each arm (currently, YELLOW and
BLUE) is also a predefined frame; these frames are "read only" in the
sense that they may not appear to the left of an assignment arrow.
The values of YELLOW and BLUE are implicitly modified by arm motions,
however. The rest positions of the two arms are YPARK and BPARK,
which are also read-only.
Frames are described by a pair of vectors: one for position
and one for orientation. An example of a frame expression is [LOC :
ORIENT] where LOC is a vector specifying location, and ORIENT is a
vector for the orientation (with respect to the table). It is
possible to ATTACH one frame to another; this has to do with world
models, and will be discussed more fully later. The basic idea is
that whenever the value of the parent frame changes, all the frames
fixed to it are assumed to have moved with it. Examples:
FRAME F1, F2;
F1 ← [V1 : V2];
F2 ← F1 ∂ -V2;
A PLANE is constructed from two vectors: the plane passes
through the first vector, and the outward-facing normal is in the
direction of the second vector. The syntax is VECTOR1 \ VECTOR2.
Thus, the surface of the table is (0 0 0)\ Z.
Planes divide the universe into three sets with respect to
the plane: inside, on, and outside. Outside are all points which
are on the side of the plane towards the outward-facing normal. To
determine where a point lies with respect to a plane, that is,
whether it is inside, on, or outside the plane, use the expression
VECTOR . PLANE. It is a scalar whose absolute value is the shortest
distance from the vector to the plane, and whose sign is negative if
the vector is inside the plane, 0 if the vector is on the plane, and
positive if the vector is outside the plane.
It is occasionally useful to construct a plane from four
scalars: the first three are the outward pointing normal vector
(which will be normalised if necessary); the fourth is the opposite
of the distance to the origin (of table coordinates). The way to
express such a plane is like this: [S1 S2 S3 S4].
Examples:
PLANE P1, P2;
P1 ← LOC(F1) \ (F1*X); COMMENT: Y-Z plane of F1;
P2 ← P1 + (P1.(0 0 0))*NORMAL(P1); COMMENT: Moves P1 to origin;
S1 ← V1 . P1;
P1 ← [2 4 3.2 8.1]; COMMENT: Fairly meaningless;
A TRANS is an operator acting on vectors, frames, planes, and
other transes. It is defined as the relation between two frames. An
example is FRAME1 → FRAME2. The value of this trans applied to
FRAME1 is FRAME2. That is, (FRAME1→FRAME2)*FRAME1 is identically
equal to FRAME2. A trans can be built up from a rotation and a
translation; the expression is [TRANSLATION | ROTATION]. Note that
rotation is applied first. Some people find it helpful to think of
frames as transformations: The transformation associated with a frame
A is "TABLE → A". When a frame is used in a context demanding a
transformation, it will be understood as a shorthand for the trans
leading from the table. Transes operate on the left. Examples:
TRANS T1, T2;
T1 ← F1→F2;
V1 ← T1*V2;
T2← T1*T1;
ARITHMETIC
Here is a summary of the arithmetic expressions available.
They are grouped by the type of their values. These abbreviations
are used: `s' = scalar , `v' = vector , `f' = frame, `p' = plane, `t'
= trans.
scalar expressions:
s + s scalar addition (commutative)
s - s scalar subtraction
s * s scalar multiplication (commutative)
s / s scalar division
v . v dot product of two vectors (commutative)
| v | magnitude of vector
p . v signed distance from vector to plane
vector expressions:
(s s s) forming a vector from three scalars
s * v dilation of a vector
v + v vector addition (translation of the first vector by
the second) (commutative)
v ∂ v rotation of the first vector by the second
t * v transformation of a vector
f / f difference (rotation) between two frames
plane expressons:
frame expressions:
[v : v] forming a frame from location (first vector) and
an orientation (second vector)
f + v translating a frame; modifies only the location part
f ∂ v rotating a frame; modifies only the orientation part
t * f transformation of a frame
plane expressions:
v \ v formation of a plane. Goes through first vector, outward
pointing normal is in direction of the second vector.
[s s s s] formation of a plane. First 3 scalars form outward-pointing
normal; last scalar is opposite of distance to (table)
origin.
p + v translation of a plane by a vector
p ∂ v rotation of plane (about table origin) by a vector
t * p transformation of a plane by a trans
trans expressions:
f → f transformation which leads from the first frame to
the second
[v | v] composing a translation, then a rotation to make a trans
Even though the translation is written first,
it is applied after the rotation.
t + v translating a trans; modifies only the translation part.
t ∂ v rotating a trans; modifies only the rotation part.
t * t composing two transes. Transes operate on the left.
PREDEFINED CONSTANTS AND VARIABLES:
π is 3.14159...
TABLE is a frame which has standard table coordinates.
BLUE is the location of the blue hand.
YELLOW is the location of the yellow hand.
BPARK is where the blue hand parks.
YPARK is where the yellow hand parks.
X is (1 0 0).
Y is (0 1 0).
Z is (0 0 1).
Any expression preceeded with the symbol "#" means "the planning value
of this expression", that is, a constant is substituted for the entire
expression in the expander.
EXTRACTION FUNCTIONS:
LOC(FRAME) is a vector whose value is the location of the frame.
ORIENT(FRAME) is a vector whose value is the orientation of the frame.
XSCAL(VECTOR) is the X coordinate of the vector.
YSCAL(VECTOR) is the Y coordinate of the vector.
ZSCAL(VECTOR) is the Z coordinate of the vector.
NORMAL(PLANE) is the outward facing normal vector of a plane.
SOME EXAMPLES OF ARITHMETIC EXPRESSIONS
In the following examples, assume these declarations:
FRAME F1, F2, etc;
VECTOR V1, V2, etc;
SCALAR S1, S2, etc;
PLANE P1, P2, etc;
A unit Y vector in F1:
F1*(0 1 0)
F1 * Y
F1's Z vector as seen from F2:
(F2→F1) * (0 0 1)
(F2→F1) * Z
V1 rotated 90 degrees about the table's Z axis:
UNITS EULER;
V1 ∂ (90 0 0)
F1's Y-Z plane:
LOC(F1) \ (F1*X)
A plane 3 units above the table:
(0 0 3) \ Z
(3*Z) \ Z
MOTION SPECIFICATIONS
COMPILE-TIME AND RUNTIME CONSIDERATIONS
All motion statements cause the compiler to make some plans
for the eventual execution of the motion. These plans are more or
less complicated, depending on the exact type of motion requested.
Those motions which depend on the value of some frames as parameters
to the action will be planned using the compile-time planning values
for all relevant frames.
Immediately before the arm starts moving on a trajectory, the
plan is modified to bring it into line with current values of frames.
The result of this last-minute modification is that if there is any
discrepancy between the runtime and compile-time understanding of
where any frame is, the servo will place the arm in the right place
nonetheless. There are limits to the proper use of this feature; if
the planning value is seriously in error (and this can mean anywhere
from a few inches to a foot, depending on the arm being used and its
configuration), then the attempt to make last-minute corrections will
either overstrain the arm or impair force and free sensing (discussed
below). It is the user's responsibility to foresee such
discrepancies in the planning value and to branch her program so that
several moves are planned (with ASSERT statements to inform the
compiler of the assumptions being used). The IF-THEN-ELSE statement
will be useful in performing the correct branch at runtime. Its
condition will most likely involve the location of a frame.
The last step of any motion is the reevaluation of the
location of the hand, and the updating, if necessary, of the values
of all frames attached to it.
SIMPLE MOVES
A move is simple if it involves only one arm. There are two
varieties of move: MOVE and GO. The former causes a smooth
trajectory to be compiled. Such a trajectory is the result of
splining together polynomial segments (usually third degree,
occasionally fourth) for each arm joint seperately. This trajectory
calculation is somewhat time-consuming, and is done completely at
compile time. The GO form lets the servo do all the calculation, and
all that the compiler generates is a list of points that the arm
should go through (basically, just the start and the stop points). In
this mode, the arm will stop after each segment of the motion. In
either case, the arm is expected to travel from its current position
to the final position, passing through any specified intermediate
positions. The standard way to avoid the table is to begin motion
directly away from it and to end motion directly toward it. There is
a default offset associated with each frame, called its "deproach",
which is used to calculate the first and the last of the
intermediate, or "via" points. The deproach of a frame is stored as
part of the world information.
An example:
MOVE YELLOW | Smooth motion, for yellow arm
TO FROBGRASP | Name of (frame) destination
VIA SWING1, SWING2 | Two via-points
The first implicit via point will be the deproach point for whatever
frame at which the yellow arm is currently positioned. The last
implicit via-point will be the deproach point for frobgrasp.
At each of the via-points, several conditions may be
specified. These are velocity and upper or lower bounds on the time
required to reach this frame from the previous one on the list. Also,
one may specify that a piece of code is to be initiated when a VIA
point is achieved; this is done with a THEN construct. The statement
following THEN may not be a jump or a motion statement for the same
arm.
An example:
VIA F1 (VEL=3*Z), F2 THEN ENABLE CH1, F3 (VEL=0,
DURATION=5).
This specifies three via points. At the first, the velocity is to be
3*Z, at the second a scalar variable is to be set, and at the third
the velocity is to be 0 and it should take 5 seconds to get there
from F2.
Certain things must be specified for any move. First is the
arm which is to be moved. It can be named directly (as YELLOW or
BLUE) or by naming a frame which is to be moved: If FROB is attached
to a hand, it is perfectly reasonable to request that the frob be
moved to a particular location. So if FROB is a frame attached to
BLUE, then both FROB and BLUE are "controllable frames"; MOVE FROB is
perfectly legal. A discussion of frame attachment can be found in the
world model specifications.
Next, the destination frame must be specified. TO F1 means
that at the end of the motion, the controllable frame (assume it is
an arm) should coincide with the frame F1. MOVE FROB TO F2 means
that at the end of the motion, FROB coincides with F2. A notational
convenience about destinations: They can be specified in terms of
where the controllable frame is at the start of the motion. The
symbol for this is ⊗. That is, ⊗ is a frame which is the location
and orientation of the controllable frame at the start of the motion.
Thus, ⊗ + (0 0 1) is a frame 1 unit above the starting place (in
table coordinates).
OPTIONS FOR MOVES
ON requests that certain conditions be continually monitored
during motion. These can be conditions of any sort, including flag
checking, force checking, and time checking. If any monitored
condition triggers, the DO part associated with it will be executed.
The "block" of a motion-based ON monitor is the motion statement
itself; exiting the motion will disable the test.
Several functions can be tested continually; these include
force along a vector (FORCE(V)), time since beginning (DURATION), and
the force between the fingers (SQUEEZE).
One more "function" is testable: SUCCESS. This becomes true
when the motion terminates due to either having reached its
destination, or some ON-monitor having executed the statement
"SUCCEED" in its conclusion. (SUCCEED also stops the arm, of
course.)
An example:
ON FORCE(Z)>10 DO
BEGIN OUTPUT("OUCH"); STOP END.
TRACING is another option. It allows the user greater
control over the exact trajectory chosen for the move. The path can
be traced at whatever speed desired. The path, or "parameterized
frame", is a specification of what frame the arm is to go through
for each value of the parameter. Of course, one also specifies the
relation between the parameter and real time. It is also possible to
state the grain of the motion and the tolerance that is acceptable
(as a distance in 3-space).
An example:
MOVE YELLOW
TRACING CENTER + (COS(P),SIN(P),0)
FOR P ← 0 BY.1 UNTIL 2*π;
should move the yellow arm in a circle around CENTER.
Next comes the option of MAINTAINING ORIENTATION. This
causes the trajectory computed by HAL to try to maintain the same
hand orientation throughout the motion. Of course, the final
orientation must be the same as the initial orientation for this to
work at all.
USING lists a set of modes under which the motion is to be
performed. These can include duration control, force applied in
some direction, which directions should be free from position
feedback, and what the departure and approach should be (if it is
desired to override the defaults, which are properties of the frames
involved at the beginning and end of motion).
Duration refers to the time elapsed since the start of
motion. In an ON-monitor, one can check for duration becoming too
long. In the USING construct, duration is merely a note for how long
the trajectory should be planned to take. One can use ≥,=,or ≤ for
this, although ≤ is most likely risky.
Force specifies both a direction and an intensity. During
the motion, an attempt will be made to apply the required force.
This is done by applying certain forces in some combination of arm
joints. Which arm joints are affected is decided by the compiler; if
the motion is long, it is likely that the particular joints applying
force will be scheduled to change during the motion, as the aspect of
the arm changes. To get a force in the hand's Z direction, say, one
would write FORCE = @ * Z, where @ is a symbol meaning "the location
of the controllable frame, as continuously changing during motion."
A free direction is one in which all position errors are
ignored by the servo. As for forces, the compiler translates this
into a set of joints which are to have the position feedback
disabled, and this set may vary throughout the motion. Once again,
the @ may be used to refer to the controllable frame as it moves.
It is possible to free more than one direction, or apply
force in more than one direction. In this case, the directions
specified for force must be orthogonal, as must the directions
specified for free. This restriction is enforced by the requirement
that multiple forces and frees all be set with respect to the
cardinal directions of one frame. Examples:
USING FORCE = FROB*Z, FORCE=FROB*X, FREE=HAND*Y, FREE=HAND*Z
USING FORCE = (2 1 0), APPROACH = FROB * Z
USING FREE = X, FREE = Y, DEPARTURE = NULL
Since both force and free are translated by the compiler into
special handling of certain joints, surprises can result from large
discrepancies between the planning values and the actual runtime
values. The motions will go through the right places, but the
directions of force and freedom may be wildly wrong.
The notions of force and free are hardware-dependent; they
depend on the particular arm in use. Hopefully, as more
sophisticated arms become available, USING can be extended to handle
whatever new capabilities exist.
COMPLEX MOVES
A complex move is one which involves more than one arm at a
time. A distinction can be made between moves which merely require
simultaneous acquisition of "agreement points" (let us call this weak
synchrony), and those which require true coordinated motion
throughout (strong synchrony).
WEAK SYNCHRONY
Weak synchrony is achived by pairing frames to make composite
VIA points and destinations. A paired frame has the form: {F1, F2}.
Here is an example of a move statement using paired frames:
MOVE {YELLOW, BLUE}
VIA {Y1,B1},{Y2,*},{Y3,B2}
TO {Y4,B3}
ON {FORCE(Z)>3,*} DO STOP
The via list is composed of a set of paired frames, where *
indicates "don't care". In the example shown, the arms start
together, achieve Y1 and B1 simultaneously, the yellow arm passes
through Y2, and together they pass through Y3 and B2.
It is now more cumbersome to specify ON monitors, or
conditions in general. The paired construct applies for all the
optional fields; thus, one can write
USING FORCE={3*Z,(2*Y)*@} to get the yellow arm applying a
force of strength 3Z, and the blue one to have a force of strength 2Y
in the coordinate system of the blue hand.
The meaning of ⊗ and @ is now relative to which side of the
pair they occupy; in the example above, the left side always refers
to the yellow arm, and the right side to the blue. To override this
convention, one may use expressions like "@.YELLOW", or "⊗.BLUE".
The meaning of STOP in the example above is extended to both
arms at once; in order to specify only one, it is necessary to say
"STOP YELLOW" or "STOP BLUE".
STRONG SYNCHRONY
Strong synchrony involves one concept not included above: The
ability to specify the location of one arm throughout the motion in
terms of the location of the other arm. The construct which allows
this specification is COORIDINATING; it allows one to give an
expression for the location of one of the two arms. Suppose we wish
to keep both arms in "lockstep", that is, the blue arm should retain
its relative position to the yellow arm throughout the motion. (This
might be necessary for lifting some object by its two ends.) One way
to code this task is as follows:
MOVE {YELLOW, BLUE}
TO {Y1, *}
VIA {YA,BA},{YB,BB}
COORDINATING LOC.BLUE = LOC.YELLOW + ⊗.BLUE - ⊗.YELLOW
USING FREE = {*, @.YELLOW - @.BLUE}
{MAINTAINING ORIENT, MAINTAINING ORIENT}
SEARCHES
A SEARCH is very much like a move. It is a means of
specifying repeated action in a spiral. As with a MOVE, it is
necessary to name a controllable frame which is to be moved. The ON
construct is exactly as for MOVEs.
One must stipulate what the plane of the search is to be.
This is accomplished in either of two ways: ACROSS <plane> means the
search is to take place in the plane specified. If the controllable
frame (say the hand) is in fact not in that plane at the start, then
the plane parallel to the given one through the hand will be used. It
is assumed that the hand begins at the center of the search. The
other alternative is to say NORMAL_TO <vector>. This will specify
the plane you want for the search.
The size of the increment is specified in a USING construct.
An example is USING INCREMENT = 3.
The servo does almost all the calculating for searches; it is
fed the normal direction and the increment size.
Most important for the search is the REPEATING construct. It
is by this that one specifies what motion is to be performed at each
iteration of the search. It is advisable that the motion cause the
arm to return to the point at which it began, in order to assume the
same plane at the onset of each iteration. If this is not done, then
the servo will move it back each time anyway. When the search
succeeds (and it is the duty of the user to specify what success
means for each search) the search can be terminated in either of two
ways: by setting a flag in the REPEATING and checking it with an ON,
or by using the construct DONE inside the REPEATING at the right
place.
Here is a complete example:
SEARCH YELLOW
ACROSS P1
REPEATING
BEGIN
FRAME SET;
SET ← YELLOW;
MOVE YELLOW TO ⊗-Z
ON FORCE(Z) > 3 DO
BEGIN
FLG ← 1;
DONE;
END;
GO YELLOW TO SET;
END
ON FLG=1 DO STOP
CENTER
It happens at times that the hand is positioned around an
object, and it is desired to center the hand about it, closing the
fingers at the same time. The arm is meant to move over to accomodate
the object, should it be slightly off-center with respect to the
hand.
All this is accomplished by means of the CENTER command. As
with the SEARCH command, it takes as an argument the plane in which
the centering is to take place, either by the construct ACROSS
<plane> or by NORMAL_TO <vector>. The use of ON is just as in a
search or any other motion.
Here is a simple example:
CENTER BLUE
NORMAL_TO Z
ON SQUEEZE > 4 DO STOP
DEVICE CONTROL
STOPPING
Generally, an arm will stop its motion when it has achieved
its destination. Often it is necessary to stop it prematurely, for
example, if some error condition is detected. The statement STOP
YELLOW causes the yellow arm to be unconditionally stopped, and any
motion statement operating it will terminate. Each device has a name,
and can be stopped by name. Currently, the legal device names are
YELLOW, BLUE, VICE, DRIVER (an electric screwdriver), YFINGERS,
BFINGERS (The fingers of the two arms). STOP without any device name
is only legal within a motion command; it stops whatever device that
command is operating.
OPERATING OTHER DEVICES
There is a general command for operating devices other than
arms; it is hoped that this will be flexible enough for any device we
are likely to use (if not, we will add special new forms). Assume we
have the device TURNTABLE, which is capable of moving at any velocity
and for any length of time, but which cannot go to a particular set
point. Then the syntax would be this:
OPERATE TURNTABLE
WITH VELOCITY=3
WITH DURATION=8
The idea is that the WITH construct will suffice to account for any
special data (in this case, velocity and duration) peculiar to the
particular device. The OPERATE statement also allows the ON
construct, so it can test for special conditions and take appropriate
actions.
SCREWDRIVER CONTROL
The screwdriver is a hand-held device which can be run at a
range of speeds, in either direction. By convention, a positive
velocity means clockwise, and a negative velocity means
anticlockwise. The relevant reserved word is VELOCITY, which is
equated with the name of a scalar variable, which will be queried
each time the screwdriver servo wakes up to determine how much
voltage to supply the moter. This allows the velocity to change
during the operation of the device, perhaps under the control of a
parallel process which is monitoring some conditions.
An example:
OPERATE DRIVER
WITH VELOCITY=SP
ON DURATION>4 DO STOP
ON DURATION>2 DO SP ← 2*SP
FINGER CONTROL
Each arm has two fingers at the end which are capable of
closing and opening at various speeds. The relevant reserved words
are OPENING, which is to be set to the desired (scalar) opening, and
VELOCITY, which is to be set to the speed desired. It is possible to
refer to the scalar variable SQUEEZE, which indicates the force being
applied by the fingers.
An example:
OPERATE FINGERS
WITH OPENING=4
WITH VELOCITY=2
ON SQUEEZE > 3 DO STOP
WORLD MODEL SPECIFICATION
***** MUCH OF THIS WILL COME FROM ASRT.DOC[HAL,RHT]
THE CHECK STATEMENT
Since library routines will be commonly used, it is necessary
to have some way of checking that necessary preconditions are met as
the first steps of the library routine. The way this is done is with
the CHECK statement. A simple example is this: CHECK X=3 ∧ Y>5. The
contents of the check may be any boolean expression, including checks
on the current world model. ASSIGNMENTS
The second way that the world changes is after every
assignment statement. The right-hand-side of the assignment is
evaluated using planning values, and the result is placed as the
planning value of the left hand side. Thus if the statement W ← X*Y
were to be executed immediately following the assertion shown above,
the planning value for W would become 0 < W < 28. Construction of
complex datatypes, like vectors, from scalars which have assertions
on them has the effect of carrying those assertions along as part of
the planning value of the left hand side.
In this context, any motion statement is like an assignment
to the hand's value. The planning effect of MOVE YELLOW TO F1 is
that the planning value of the yellow hand becomes the planning value
of F1.
ATTACHMENT
Assembly often involves affixing one object to another. HAL
has a mechanism of automatically keeping track of the location of a
subsidiary piece of the assembly as its base is moved; the mechanism
is called ATTACHMENT. For example, there might be a frame called
PUMP and a frame called BASE. At some stage in the assembly, the
pump is bolted to the base. At this time it is appropriate to
include the statement "ATTACH PUMP TO BASE". The effect of this is
severalfold: It informs the compiler that motions of BASE are to
effect the location of PUMP, it generates the assertion "ASSERT FACT
(ATTACHED PUMP BASE)", and it causes code to be generated for the
runtime which will automatically update the value of PUMP every time
BASE is changed. Please note that the ATTACH statement does not act
as a library routine invocation; it does not generate code to
actually perform the bolting operation. The statement merely informs
the HAL system that at this stage in the execution of the program,
PUMP is to be considered attached to BASE.
If PUMP should be moved while attached to BASE, the value of
BASE itself will not change, but the attachment will remain for the
new relative positions of PUMP and BASE. Occasionally it is desired
that the attachment be symmetric, so that motion of either frame will
cause the other to move. This is done by including the reserved word
RIGIDLY in the attach statement: "ATTACH PUMP TO BASE RIGIDLY".
When an attachment is made, a trans is invented to store the
relative positions of the two objects; in the example we have been
using, that trans will take the value (BASE → PUMP). The user may
wish to access this trans directly, and perhaps even to change its
value. To do this, include the clause "BY <trans>" in the attach
statement; this will cause the invented trans to have the supplied
name.
If the value of the trans is modified in a non-rigid (that
is, assymetric) attachment, the effect is to move the subsidiary
frame. If the value of the trans changes in a rigid (that is,
symmetric) attachment, then neither frame will change its value until
one of them explicitly gets a new value; then the other will spring
to a new position, as determined by the trans.
It is possible to make chains of attachments, possibly
involving some rigid attachments and some non-rigid ones.
To undo an attachment, execute the statement "DETACH PUMP
FROM BASE". This will remove the attach structure between them, and
will discard the invented trans (unless it was named, of course). Two
assertions will also be automatically generated: "DENY FACT (ATTACHED
PUMP BASE); ASSERT FACT (WAS_ATTACHED PUMP BASE)". The latter
assertion is used in calculation of default deproach points.
GRAPH-STRUCTURE BUILDING
SAVING AND RESTORING
The statement SAVE WORLD IN W1 will cause all the world at
that point in the planning to be written out into a file called
W1.WLD. The statement RESTORE WORLD FROM W1 will read in this file
and set up the world as it was when saved. This is particularly
useful for recovering when the arm runs into trouble; it makes it
unnecessary to begin the planning from scratch. It is also possible
to improve the planning values of frames after a period of execution;
this is done by the statement RESTORE WORLD FROM RUNTIME.
USES OF THE WORLD MODEL
***** SEE ASRT.DOC[HAL,RHT]
The world model is used for several purposes: 1) to allow
trajectories to be calculated at compile time. 2) to allow the
expander to conditionally expand library routines.
CONDITIONAL EXPANSION
The way to query the state of the world is with the IFW construct.
For example, in order to write some code to bring the arm to park only
if it is not already there, on can say:
IFW BLUE ≠ BPARK THENW
MOVE BLUE TO BPARK;
Fhis is especially useful in interfacing library routines with the
programs which call them. The values used in the booleans of
conditional expansions are always planning values. The values
of properties are also accessible to the conditionals.
OVERVIEW OF THE RUNTIME
The runtime is a set of programs residing in the PDP-11.
We will discuss control structures and data structures.
CONTROL STRUCTURES
PROCESS TYPES
There are several types of processes any number of which can
be active at any time:
1) Interpreters
2) Joint servos
3) On-monitors
An INTERPRETER is a process which is executing arithmetic or
other stack-oriented instructions, not one of the moves. As soon as
it encounters a move, it instantiates the required joint servos and
on-condition checkers and waits for the termination of the move
before continuing. Each interpreter also has a reserved cell in
which it stores information on where it currently is in the source
code; this is useful for debugging.
A JOINT SERVO is a process whose task is to servo one joint
of a moving arm, according to the planned trajectory for that joint.
When finished, the servo stops the joint and disappears. If the
joint should be stopped by some other process, the servo cleans up
the mess and dismisses.
An ON-MONITOR is a process which continually checks for some
condition. If that condition should appear, then those actions
specified by the compiler as critical are done immediately (in a
non-interruptable fashion); for the rest, the monitor sprouts an
interpreter. The ON-monitor can be in two states: enabled and
disabled. The checking is only done while the monitor is enabled.
The monitor disappears only when the system kills it.
INTERPRETABLE CODE
The basic instruction emitted by the compiler is one 16-bit
word. The first 8 bits are the opcode, and the last 8 are used to
form the operand address, if the opcode needs one. Addressing modes
are either immediate, in which case the next word has the address, or
relative (to the program counter). Immediate addressing is indicated
by the second byte being 0. Anything else is relative addressing;
bit 8 (the lefthand bit of the righthand byte) is a sign bit; thus
one can look 127 locations forward or backward; the full word address
will be found at this place. Full-word adresses can be indirect;
this is indicated by a high-order bit (ie, bit 0) being 1.
Indirection can proceed to any level.
STACK OPERATORS
pushadr <arg> puts <arg> on top of the stack. It is assumed that
<arg> is the address of a variable.
pushval <arg> puts value of variable pointed to by <arg> on stack.
gets good value, if necessary.
pop pops the stack.
copy <num> finds the <num>'th element down in the stack, and copies
it to the top.
flush clears the stack.
store <arg> pointer at top of stack copied into value pointer at <arg>;
stack is popped.
SINGLE FRAME OPERATIONS
solve takes a pointer to a frame value cell from top of stack.
Generates arm solution (if necessary) and stores in the
value cell. The stack is popped.
invert the inverse of the value cell at top of stack goes to
top of stack; old top popped.
ARITHMETIC
For the following, the args are on the stack, are popped
after the operation, the answer pointed to on top of stack. Earlier
arguments deeper on the stack.
s+s scalar addition. 2 args.
s-s scalar subtraction. 2 args.
s*s scalar multiplication. 2. args.
s/s scalar division. error if second arg is 0. 2 args.
|v| magnitude of vector. 1 arg.
v.v dot product. returns scalar.
(sss) forms vector from 3 scalars. 3 args.
s*v dilation of vector. 2 args. scalar first.
v+v vector addition. 2 args.
v∂v vector rotated by vector. second arg is rotation. 2 args.
t*v transformation of vector. trans first. 2 args.
[v:v] forms frame from 2 vectors. first is loc, second orient. 2 args.
f+v translation of frame. 2 args. frame first.
f∂v rotation of frame. 2 args. frame first.
t*f transformation of frame. 2 args. frame first.
f→f forms trans from two frames. 2 args. f1'f2.
[v|v] forms trans from two vectors. 1: trans; 2: rot.
t+v translates trans. 2 args. trans first.
t∂v rotates trans. 2 args. trans first.
t*t composition (to the left) of two transes.
tinv inverse of trans
EXTRACTION AND COMPOSITION
loc location of frame replaces it at top of stack.
orient orientation of frame replaces it at top of stack.
xscal x coordinate of vector replaces it at top of stack.
yscal y coordinate of vector replaces it at top of stack.
zscal z coordinate of vector replaces it at top of stack.
INSTANTIATION, DESUBSTATIATION, AND TRANSSUBSTANTIATION
sprouti <arg> start up an interpreter with name <arg>. The location
of its block of code is on the stack; pop it.
sprouto <arg> start up an on-monitor with name <arg>. The location
of its block of code is on the stack; pop it.
enable <arg> the on-monitor with name <arg> is enabled.
disable <arg> the on-monitor with name <arg> is disabled.
delayme wait until all descendent (non on-monitor) processes are dead.
Then kill descendent on-monitors and continue.
die terminate this process. Automatically first calls "delayme".
JUMPS
These have not yet been written.
nop no-op.
ARM AND DEVICE CONTROL
move <arg> <arg> points to the move vector.
go <arg> <arg> point to the GO table.
search <arg> <arg> points to the search vector.
stop <arg> <arg> encoding of what devices must be stopped.
INPUT AND OUTPUT
Some sort of I/O will be implemented, most likely including string
output to the supervisor, error message output, and input (from supervisor
or from coresident routines) of value cells.
DEBUGGING AIDS
source <arg> notes that <arg> is where the interpreter is now in
source code.
tellsource output current source location to the 10.
step begins step mode, which does one interpretation at a time,
requires message to continue.
offstep turns off step mode; normal speed is resumed.
DATA STRUCTURES
VALUE CELLS
Each variable has a value cell, either associated with it
directly or pointed to by the graph structure. Each datatype has its
own format for the value cell. Fixed-point numbers are used
throughout.
Scalars are stored in a single word, in fixed-point format.
Vectors are stored in four consecutive words. The fourth
entry is usually 1; the arithmetic routines are optimised for such
normalised vectors. To normalise a vector, divide each entry by the
fourth one.
Planes are also stored in four words. The first three
represent an outward-facing normal, and the last is the negative
distance to the (table) origin.
Frames are stored as 4x4 arrays, by columns. This includes
only the O, A, and P columns of the 4x4 array. In addition to the 9
matrix positions, there are 6 words set aside for the joint angles
associated with the frame, and one validity bit to signal the
correctness of those joint angles. They are calculated only if
needed. This happens if the frame is being used as a point in a
trajectory. A validity bit is associated with the joint angles; it is
made true when they are calculated, and false when the 4x4 part of
the frame changes.
Transes are stored in two 4x4 arrays: One is the same as the
format for frames, and the other is the inverse.
GRAPH STRUCTURES
Those variables participating in the graph structures have a
special node cell.
NODE CELL
invmark -- =0 if value is valid, otherwise invalid (note: the
evalnode algorithm uses a "time" to detect cycles. Therefore, this
field needs to be (at least) 16 bits.
value -- pointer to a value cell.
calculator -- points to a list of calculator cells
changer -- points to a block of interpretable code. There are
a few special-purpose changers which do not point to any code, but
are used as shorthands. These include "VALUE ← NEW".
dependents -- points to a list of dependents
type -- encoding (in several bits) of datatype.
CALCULATOR CELL
link -- link to next on the chain (there can be more than one
calculator for a node).
needed -- points to list of variables needed for this
calculator. The dependents cell format is used for the needed list.
code -- points to a block of interpretable code.
DEPENDENTS CELL
link -- link to next on the chain (there can be more than one
dependent of a node).
dep -- points to the node cell of one dependent.
ALGORITHMS FOR USE OF GRAPH STRUCTURE
PROCEDURE invalidate (POINTER(NODE) n);
IF invmark(n)=0 THEN
BEGIN COMMENT: This cell currently marked valid;
POINTER p;
invmark(n)← -1;
p ← dependents(n);
WHILE p≠NULL DO
BEGIN COMMENT: Mark all dependents as invalid;
invalidate(p);
p ← link(p)
END
END;
PROCEDURE change (POINTER(NODE) n; POINTER(VALUE) vnew);
BEGIN
POINTER(VALUE) vold;
invalidate(n);
vold ← value(n);
value(n)←vnew;
p ← changer(n);
WHILE p≠NULL DO
BEGIN COMMENT: Handle all changers;
APPLY(code(p),vold,vnew);
p ← link(p);
END;
invmark(n) ← 0;
END;
POINTER(VALUE) PROCEDURE getvalue (POINTER(NODE) n);
BEGIN
IF invmark(n)≠0 THEN evalnode(n, time ← time+1);
RETURN(value(n));
END;
PROCEDURE evalnode (POINTER(NODE) n, INTEGER t);
BEGIN COMMENT: Put a good value in the value cell of n.
t is used to break cycles;
IF invmark(n)=0 ∨ invmark(n)=t THEN RETURN;
invmark(n) ← t;
p ← calculator(n);
WHILE p ≠ NULL DO
BEGIN "cloop"
POINTER(dependent) d;
d ← needed(p);
WHILE d ≠ NULL DO
BEGIN
evalnode(dep(d),t);
IF invmark(dep(d))≠0 THEN
BEGIN
p ← next(p);
CONTINUE "cloop";
END;
d ← next(d);
END;
value(n)←APPLY(code(p), args(p));
invmark(n)←0;
RETURN;
END;
END;
TRAJECTORIES not yet ready for perusal
1) Code is executed interpretatively to set up temporary frames
necessary for this motion.
2) The "start move" pseudo-op is encountered; it points to the
location of a vector of joint start addresses (for 6 joints, need a
vector of 12 adresses, because each joint needs both its location and
its inertia tables).
3) A scan is made for each joint down its chain of location tables,
during which the coefficients for each segment are modified by a 5th
order polynomial to bring them into conformity with the frames
specified, if necessary.
4) A process is sprouted for each joint which will service that
joint. Actually, only one copy of that process exists, and each
joint has its own data area which contains a) servo constants for
that joint, b) location counters into the two types of tables, c)
precalculated values relevant to the next awakening.
5) Each process, on each awakening, checks the clock to make sure it
was awakened at the right time (fatal error otherwise), outputs the
precalculated drive, decides how long it is willing to sleep,
reserves an awakening slot (more on these soon) in the calendar,
computes the drive for that time, and goes to sleep.
6) As each joint finishes its whole trajectory, it requests that the
monitor kill it. When all the joints have been killed, the monitor
(which knows that a move was in progress) returns control to the
interpreter (which is itself a process) where it left off.
Termination of a move is quite simple: The joint status word, which
is global to the entire runtime, is just set for each joint affected
to a value which means "unrunnable" The next time the servo is
awakened, it will notice this and request euthanasia. The
termination also requires that the motors be stopped, and the brakes
applied, and the resting point of the arm determined.
Some care must be taken to prevent two interpreters proceeding at the
same time under conditions whereby one should really be waiting for
the other. Specifically, during a move, the interpreter that
initiated that move is suspended until it is complete. Therefore, if
an on-test causes another interpreter to start, the suspended
interpreter must remain suspended until the new one dies.
TRAJECTORY TABLES
The following are necessary properties of trajectory tables:
Must state which frames are used, so the servo can do appropriate
update.
Must be perspicuous enough to allow servo to find the things which
it must update.
Must allow escape to interpret mode at end of each segment for
each joint, in order to initiate new motions or "on" tests.
A trajectory table is a set of joint-segment tables. Each
joint-segment table is intended to give instructions for the servoing
of one joint along one segment of the path. There are two types of
such tables: location and inertia. The servo follows each of these
simultaneously and asynchronously.
FORMAT OF THE LOCATION-JOINT-SEGMENT TABLE: This table is ten words
long.
words 1,2,3,4,5,6: coefficients a5,a4,a3,a2,a1,a0 of the trajectory.
Polynomial is normalised for tε[0,1].
word 7: Duration of segment in milliseconds.
word 8: Pointer to next location-joint-segment table for this joint.
If this is the last segment, word 8 is 0.
word 9: Pointer to frame which is to be assumed at end of this
segment. If no particular frame, then this is 0. This is used in a
preprocessing step to modify the coefficients of the polynomial; at
swing time it is not needed.
word 10: If not 0, then a pointer to a location of interpretable
code where an interpreter is to be instantiated and begun. This is
for the THEN part of VIA lists.
FORMAT OF THE INTERTIA-JOINT-SEGMENT TABLE: This table is 7 words
long.
words 1,2: Coefficients j1,j0 of joint inertia polynomial, normalized
for tε[0,1].
words 3,4: Coefficients g1,g0 of gravity loading polynomial.
Likewise normalized.
word 5: Duration of segment in milliseconds.
word 6: Control word, with bits for free, force, drive, nodrive, etc.
see later discussion on control words. This is copied into a global
location at start of inertia-joint-segment.
word 7: Pointer to next intertia-joint-segment table for this joint.
If this is the last segment, word 7 is 0.
GO TABLES
The following are necessary properties of go tables:
Must state list of frames to use (including initial deproach
and via-list)
Must allow escape to interpret mode at end of each segment.
A GO table is a list of frames through which the motion is to
proceed. Each is specified by its address. The first one is the deproach
of the start frame; the penultimate is the deproach of the final
frame. Following each frame address is an interpreter address, which
is the adrress of the interpreter (if any) to be invoked upon achievement
of the preceeding frame. The last frame is distinguished by an interpreter
address of -1.